import java.util.List;
import java.util.ArrayList;
import java.util.Deque;
import java.util.ArrayDeque;
import java.lang.String;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;

public class NonFA {
	private static final Character EPSILON = (char) 0;
	// Change this if we can't assume that the null Characteracter isn't used

	private List<State2> states;
	private Deque<List<State2>> opperands;
	private Deque<Character> operators;
	private int nextStateId;
	private Set<Character> input_set;
    private Map<Set<State2>,Set<State2>> epsilonmap;

	public NonFA () {
		this.states = new ArrayList<State2>();
		this.opperands = new ArrayDeque<List<State2>>();
		this.operators = new ArrayDeque<Character>();
		this.nextStateId = 0;
		this.input_set = new HashSet<Character>();
        this.epsilonmap = new HashMap<Set<State2>,Set<State2>>();
	}

    public NonFA (Set<Character> in_set) {
        this.states = new ArrayList<State2>();
        this.opperands = new ArrayDeque<List<State2>>();
        this.operators = new ArrayDeque<Character>();
        this.nextStateId = 0;
        this.input_set = in_set;
        this.epsilonmap = new HashMap<Set<State2>,Set<State2>>();
    }


    public State2 addState(boolean accepting) {
        State2 state = new State2(nextStateId, accepting);
        states.add(state);
        nextStateId++;
        return state;
    }
    
    private State2 getState(Integer i) {
        for (State2 s : states){
            if (s.getID() == i) return s;
        }
        return null;
    }
    
        
        
//NFA -> DFA stuff

        public DeterministicFiniteAutomaton toDFA(){
            Set<State2> startstate = null;
            DeterministicFiniteAutomaton dfa = new DeterministicFiniteAutomaton(input_set);
            Map<Set<State2>,Map<Character,Set<State2>>> table = new HashMap<Set<State2>,Map<Character,Set<State2>>>();
            Set<State2> currentStates = new HashSet<State2>();
            currentStates.add(states.get(0));
            Deque<Set<State2>> queue = new ArrayDeque<Set<State2>>();
            queue.addLast(currentStates);
            //finish creating the queue

            //creating the character -> set of States map
            Map<Character, Set<State2>> t = new HashMap<Character, Set<State2>>();
            //finished with set up

            while (queue.size()>0){
                currentStates = queue.poll();
                currentStates = epsilonClosure(currentStates);
                if(!table.containsKey(currentStates)){
                    for (State2 s : currentStates){
                        for (Character c: input_set){
                            if (s.getTargets(c)!=null){
                                if (t.containsKey(c)){ //if this activates a previous State has already logged transitions for this character
                                    for (Integer i : s.getTargets(c)){
                                        t.get(c).addAll(epsilonClosure(this.getState(i)));
                                    }
                                }else{
                                    Set<State2> temp = new HashSet<State2>();
                                    for (Integer i : s.getTargets(c)){
                                        temp.addAll(epsilonClosure(this.getState(i)));
                                    }
                                    temp = epsilonClosure(temp);
                                    t.put(c,temp);
                                }
                            }
                        }
                    }
                    //check this one as the start state
                    if( startstate == null) startstate = currentStates;
                    for (Set<State2> states : t.values()){
                            queue.offer(states);
                    }
                    table.put(currentStates,new HashMap<Character,Set<State2>>(t));
                    t.clear();
                }
            }
            //what we will be returning
            //this map is for giving consistent names to the new states
            Map<Set<State2>,State> names = new HashMap<Set<State2>,State>();
            //assign the new names and populate the DFA
            boolean accept;
            for (Set<State2> old : table.keySet()){
                names.put(old, new State());
                accept = false;
                for (State2 s : old){
                    if (s.isAccepting()) accept = true;
                }
                dfa.addState(names.get(old), accept);
                if( old == startstate) dfa.setStartState(names.get(old));
            }
            Set<State2> errorstate = new HashSet<State2>();
            errorstate.add(new State2());
            names.put(errorstate, new State());
            dfa.addState(names.get(errorstate), false);
            for (Character c : input_set){
                dfa.setTransition(names.get(errorstate), c, names.get(errorstate));
            }
            
            
            for (Map.Entry<Set<State2>, Map<Character,Set<State2>>> entry : table.entrySet()) {
                Map<Character,Set<State2>> trans = entry.getValue();
                for (Character c : input_set){
                    if (trans.containsKey(c)){
                        dfa.setTransition(names.get(entry.getKey()), c, names.get(trans.get(c))); 
                    }else{
                        dfa.setTransition(names.get(entry.getKey()), c, names.get(errorstate)); 
                    }
                }
                        
            }
            return dfa;
        }

                
     private Set<State2> epsilonClosure(State2 s){
            Set<State2> set = new HashSet<State2>();
            set.add(s);
            return epsilonClosure(set);
    }
                
     private Set<State2> epsilonClosure(Set<State2> s){
           if (epsilonmap.containsKey(s)){
                return epsilonmap.get(s);
            }
           Set<State2> returnStates = new HashSet<State2>();
            returnStates.addAll(s);
           for(State2 i : s){
                if(i.getTargets(EPSILON)!=null){
                    for(Integer k : i.getTargets(EPSILON)){
                        returnStates.add(this.getState(k));
                    }
                }
            }
            if(returnStates.size() != s.size()){
                returnStates = epsilonClosure(returnStates);
            }
            epsilonmap.put(s,returnStates);
            return returnStates;
    }
                
 
//Regex -> NFA stuff


	private boolean isOperator(Character c) {
		return (c=='*' || c=='+' || c=='|' || c=='(' || c==')');
	}

	private boolean isInput(Character c) { return !isOperator(c); }
	
	public boolean buildFromRegex(String r) {
		r = regexExpand(r);

		for( int i = 0; i < r.length(); i++ ) {
			Character ch = r.charAt(i);
			
			if( this.isInput(ch) ) {
				this._push(ch);
			}
			else if (this.operators.size()==0) {
				this.operators.push(ch);
			}
			else if ( ch=='(' ) {
				this.operators.push(ch);
			}
			else if ( ch==')' ) {
				while ( this.operators.peek() != '(' ) 
					if ( !this.evaluateTop() ) return false;
				this.operators.pop();
			}
			else {
				while( this.operators.size() > 0 && this.prescedence(ch, this.operators.peek()) ) {
					if ( !this.evaluateTop() ) return false;
				}
				this.operators.push(ch);
			}
		}
		while ( this.operators.size() > 0 ) if ( !this.evaluateTop() ) return false;

		if (this.opperands.size() != 1) return false;
	
		this.states = this.opperands.pop();
		this.states.get(this.states.size()-1).setAccept(true);

		return true;
	}


	private String regexExpand(String s) {
		String s_processed = new String();
		char cha, chb;
		Character first, last;

		for( int i = 0; i < s.length(); ) {
			cha = s.charAt(i);
			if( cha == '\\') {
				s_processed = s_processed.concat( "\\" + String.valueOf(s.charAt(i+1)));
				i+=2;
			}
			if( cha == '[' ) {
				first = s.charAt(i+1);
				last = s.charAt(i+3);
				String toAdd = new String();
				for( Character ch = first; ch < last; ch++ ) {
					toAdd += ch + "|"; } toAdd = "(" + toAdd + last + ")";
				s_processed = s_processed.concat( toAdd );
				i+=5;
			}
			else if ( cha == '+' ) {
				s_processed = s_processed.concat( "\\+");
				i++;
			}
			else if ( cha == '*' ) {
				s_processed = s_processed.concat( "*");
				if( (i+1) < s.length() && (s.charAt(i+1) == '(' || isInput( s.charAt(i+1))))
					s_processed = s_processed.concat("+");
				i++;
			}
			else if ( cha == '|' || cha == '(' ) {
				s_processed = s_processed.concat( String.valueOf(cha) );
				i++;
			}
			else if (cha == ')') {
				s_processed = s_processed.concat( ")" );
				if( i+1 < s.length() && (s.charAt(i+1) == '(' || isInput(s.charAt(i+1)) ))
					s_processed = s_processed.concat("+");
				i++;
			}
			else if ( i+1 < s.length() ) {
				s_processed = s_processed.concat( String.valueOf(cha) );
				chb = s.charAt(i+1);
				if( chb != '|' && chb != ')' && chb != '*') 
					s_processed = s_processed.concat( "+" );
				i++;
			}
			else {
				s_processed = s_processed.concat( String.valueOf(cha) );
				i++;
			}
		}
		return s_processed;
	}
			
	private boolean prescedence( Character ls, Character rs ) { 
		//TODO proabably should check this for correctness.

		if ( ls == rs ) return true;
		if ( ls == '*' ) return false;
		if ( rs == '*' ) return true;
		if ( ls == '+') return false;
		if ( rs == '+') return true;
		if ( ls == '|' ) return false;

		return true;
	}

	private boolean evaluateTop()    { 
		Character op = operators.pop();

		switch(op) {
			case '|': return this._union(); 
			case '*': return this._kstar(); 
			case '+': return this._concat(); 
		}

		return false;
	}

	private void _push( Character ch ) {

		State2 a = new State2(this.nextStateId++, false);
		State2 b = new State2(this.nextStateId++, false);

		a.addTransition(ch, b.getID());
		
		List<State2> new_nfa = new ArrayList<State2>();
		new_nfa.add(a);
		new_nfa.add(b);

		this.input_set.add( ch );

		opperands.push(new_nfa);

	}
		
	private boolean _concat() {
		List<State2> a; 
		List<State2> b; 

		if ( opperands.size() < 2 ) return false;

		b = opperands.pop();
		a = opperands.pop();

		a.get( a.size()-1 ).removeTransition(EPSILON);
		a.get( a.size()-1 ).addTransition(EPSILON, b.get(0).getID() );
		a.get( a.size()-1 ).setAccept(false);

		a.addAll( b );

		opperands.push(a);
		return true;
	}

	private boolean _kstar() {
		if( opperands.size() < 1 ) return false;
		List<State2> a = opperands.pop();

		State2 n1 = new State2(nextStateId++, false);
		State2 n2 = new State2(nextStateId++, false);

		n1.addTransition(EPSILON, a.get(0).getID());
		n1.addTransition(EPSILON, n2.getID());
		a.get(a.size()-1).addTransition(EPSILON, a.get(0).getID());
		a.get(a.size()-1).addTransition(EPSILON, n2.getID());

		List<State2> b = new ArrayList<State2>();

		b.add(n1);
		b.addAll(a);
		b.add(n2);

		this.opperands.push(b);
		return true;
	}

	private boolean _union() {
		List<State2> a, b, c = new ArrayList<State2>();

		if(this.opperands.size() < 2) return false;
		b = this.opperands.pop();
		a = this.opperands.pop();

		State2 newStart = new State2(this.nextStateId++,false);
		State2 newEnd   = new State2(this.nextStateId++,false );

		newStart.addTransition(EPSILON, a.get(0).getID());
		newStart.addTransition(EPSILON, b.get(0).getID());

		a.get( a.size()-1 ).addTransition(EPSILON, newEnd.getID());
		b.get( b.size()-1 ).addTransition(EPSILON, newEnd.getID());

		c.add(newStart);
		c.addAll(a);
		c.addAll(b);
		c.add(newEnd);

		this.opperands.push(c);
		return true;
	}

	public static void main (String [] args) {
		//test_other();
        
        
        //test_janzen();

		//test_joseph();
        
        test_regex(args[0]);

	}

	private static void test_joseph() {
        System.out.println("test that joseph wrote");
		String regex = "ab(1|0)*1*";
        NonFA nfa = new NonFA();
        nfa.buildFromRegex(regex);

        System.out.println("NFA:");
		System.out.println("Regex Used: " + regex);
        System.out.println(nfa);
        DeterministicFiniteAutomaton dfa = nfa.toDFA(); 
        System.out.println(dfa);
        System.out.println(dfa.minimize());
	}
 
	
	private static void test_janzen() {
        System.out.println("test that janzen wrote");
        Set<Character> alphabet = new HashSet<Character>();
        alphabet.add('0');
        alphabet.add('1');
        String regex = "0(0|1)1";
        NonFA nfa = new NonFA(alphabet);
        nfa.buildFromRegex(regex);
        System.out.println("regex:");
        System.out.println(regex);
        System.out.println("NFA:");
        System.out.println(nfa);
        DeterministicFiniteAutomaton dfa = nfa.toDFA();
        System.out.println("DFA:");
        System.out.println(dfa);
        DeterministicFiniteAutomaton minDfa = dfa.minimize();
        System.out.println("Min DFA:");
        System.out.println(minDfa);
    }

    public void test() {
        System.out.println(states.size());
        for (State2 s : states) s.test();
    }
    
	private static void test_regex(String s) {
        System.out.println(s);
		NonFA nfa = new NonFA();
        if( !nfa.buildFromRegex(s) )
			System.out.println("Improperly formed regex.");
		else {
	        System.out.println("nfa:" + nfa);
    	    System.out.println("dfa:" + nfa.toDFA());
        	System.out.println("mdfa:" + nfa.toDFA().minimize());
		}
    }

	private static void test_other() {
		Set<Character> alphabet = new HashSet<Character>();
        alphabet.add('0');
        alphabet.add('1');
        NonFA nfa = new NonFA(alphabet);
        State2 a = nfa.addState(false);
        State2 b = nfa.addState(true);
        State2 c = nfa.addState(false);
        b.addTransition('0',a);
        a.addTransition('1',a);
        a.addTransition('1',b);
        a.addTransition('0',c);
        b.addTransition('0',a);
        DeterministicFiniteAutomaton dfa = nfa.toDFA();
        System.out.println("test 1");
        System.out.println(dfa.minimize());  
        

        alphabet = new HashSet<Character>();
        alphabet.add('0');
        alphabet.add('1');
        nfa = new NonFA(alphabet);
        a = nfa.addState(false);
        b = nfa.addState(false);
        c = nfa.addState(true);
        a.addTransition('1',b);
        a.addTransition('0',a);
        b.addTransition('1',a);
        b.addTransition('0',c);
        dfa = nfa.toDFA();
        System.out.println("test 2");
        System.out.println(dfa.minimize()); 

        alphabet = new HashSet<Character>();
        alphabet.add('0');
        alphabet.add('1');
        nfa = new NonFA(alphabet);
        a = nfa.addState(false);
        b = nfa.addState(false);
        c = nfa.addState(true);
        a.addTransition('1',b);
        a.addTransition('0',a);
        b.addTransition('0',a);
        b.addTransition('0',c);
        dfa = nfa.toDFA();
        System.out.println("test 3");
        System.out.println(dfa.minimize()); 

        alphabet = new HashSet<Character>();
        alphabet.add('a');
        alphabet.add('b');
        nfa = new NonFA(alphabet);
        a = nfa.addState(false);
        b = nfa.addState(false);
        c = nfa.addState(true);
        a.addTransition('a',b);
        a.addTransition('b',b);
        b.addTransition('a',a);
        b.addTransition('b',c);
        dfa = nfa.toDFA();
        System.out.println("test 4");
        System.out.println(dfa.minimize()); 

        alphabet = new HashSet<Character>();
        alphabet.add('a');
        alphabet.add('b');
        nfa = new NonFA(alphabet);
        a = nfa.addState(false);
        b = nfa.addState(false);
        c = nfa.addState(false);
        State2 d = nfa.addState(false);
        State2 e = nfa.addState(true);
        a.addTransition('\0',b);
        a.addTransition('a',c);
        b.addTransition('a',e);
        b.addTransition('a',d);
        c.addTransition('b',d);
        c.addTransition('a',e);
        d.addTransition('b',e);
        dfa = nfa.toDFA();
        System.out.println("test 5");
        System.out.println(dfa.minimize()); 

        alphabet = new HashSet<Character>();
        alphabet.add('a');
        alphabet.add('b');
        nfa = new NonFA(alphabet);
        a = nfa.addState(true);
        b = nfa.addState(false);
        c = nfa.addState(true);
        a.addTransition('a',a);
        a.addTransition('a',b);
        b.addTransition('a',c);
        b.addTransition('b',b);
        dfa = nfa.toDFA();
        System.out.println("test 6");
        System.out.println(dfa.minimize()); 

	}

	private static void old_test() {
		boolean pass = true;
		boolean allPass = true;

		NonFA nfa = new NonFA();
		
		// list methods to test individually
		//isOperator() - d
		//should be simple
		
		pass = pass && nfa.isOperator('|') && nfa.isOperator('*') 
			        && nfa.isOperator('+') && !nfa.isOperator('a');
		for( char ch = 'a'; ch<='z'; ch++) pass = pass && !nfa.isOperator(ch);
		for( char ch = 'A'; ch<='Z'; ch++) pass = pass && !nfa.isOperator(ch);

		System.out.println("NonFA.isOperator : " + ((pass)?"passes":"fails") +".");
		allPass = allPass && pass;
		pass = true;

		//isInput() - d
		//should be simple
		
		for( char ch = 'a'; ch <= 'z'; ch++) pass = pass && nfa.isInput(ch);
		for( char ch = 'A'; ch <= 'Z'; ch++) pass = pass && nfa.isInput(ch);

		pass = pass && !nfa.isInput('|') && !nfa.isInput('*') && !nfa.isInput('+');

		System.out.println("NonFA.isInput : " + ((pass)?"passes":"fails") +".");
		allPass = allPass && pass;
		pass = true;

		//push(char) - p
		//needs nothing on the stack but requires a character argument

		for( char ch = (char) 1; ch <= (char) 255; ch++) 
			if( nfa.isInput(ch) ) {
				nfa = new NonFA();
				nfa._push(ch);
				pass = pass && (nfa.opperands.size() == 1);
		
				List<State2> testNFA = nfa.opperands.pop();
				pass = pass && testNFA.size()==2;
		
				pass = pass && testNFA.get(0).getTargets(ch).size()==1;
				pass = pass && testNFA.get(1).getTargets(ch)==null;
			}
		System.out.println("NonFA._push(char) " + ((pass)?"passes":"fails") + ".");
		allPass = allPass && pass;
		pass = true;
		
		//_union() - u
		//need 2 items on opp stack
		//do the union and then verify
		nfa = new NonFA();
		nfa._push('a');
		nfa._push('d');

		nfa._union();


		pass = pass && nfa.opperands.size()==1;
		if (pass) {
			List<State2> testNFA = nfa.opperands.pop();
			pass = pass && testNFA.size() == 6;
			pass = pass && (testNFA.get(0).getTargets(EPSILON) != null);
			pass = pass && (testNFA.get(2).getTargets(EPSILON) != null);
			pass = pass && (testNFA.get(4).getTargets(EPSILON) != null);

			/*for( int i = 0; i < testNFA.size(); i++) {
				System.out.println( "# of epsilon tarets for node " + ((Integer)i) + ": " + 
						(( testNFA.get(i).getTargets(EPSILON) == null ) ?
							"0 (null)" :
							((Integer)testNFA.get(i).getTargets(EPSILON).size())));
			}*/
			if ( pass ) {
				pass = pass && testNFA.get(0).getTargets(EPSILON).size() == 2;
				pass = pass && testNFA.get(2).getTargets(EPSILON).size() == 1;
				pass = pass && testNFA.get(4).getTargets(EPSILON).size() == 1;
			}
		}

		System.out.println("NonFA._union: " + ((pass)?"passes":"fails") + "." );

		allPass = allPass && pass;
		pass = true;

		//_concat() - c
		//need 2 items on the opp stack
		//do the concat and then verify

		nfa = new NonFA();
		nfa._push('a');
		nfa._push('b');

		pass = pass && nfa._concat();
		
		if( pass ) {
			pass = pass && nfa.opperands.size()==1;
			if (pass) {
				List<State2> testNFA = nfa.opperands.pop();
				pass = pass && testNFA.size()==4;
				if (pass) {
					pass = pass && ( testNFA.get(1).getTargets(EPSILON) != null );
					if (pass) { 
						pass = pass && testNFA.get(1).getTargets(EPSILON).size()==1;
					}
				}
			}
		}



		System.out.println("NonFA._concat: " + ((pass)?"passes":"fails") );
		allPass = allPass && pass;
		pass = true;
		
		//_kstar() - k
		//need 1 item on the opp stack
		//do the kstar and then verify
		
		nfa = new NonFA();
		nfa._push('a');

		pass = pass && nfa._kstar();

		if (pass) { 
			pass = pass && nfa.opperands.size()==1;
			if (pass) {
				List<State2> testNFA = nfa.opperands.pop();
				pass = pass && testNFA.size() == 4;
				if (pass) {
					pass = pass && testNFA.get(0).getTargets(EPSILON).size()==2;
					pass = pass && testNFA.get(1).getTargets(EPSILON) == null;
					pass = pass && testNFA.get(1).getTargets('a').size() == 1;
					pass = pass && testNFA.get(2).getTargets(EPSILON).size()==2;
					pass = pass && testNFA.get(3).getTargets(EPSILON) == null;
				}
			}
		}

		System.out.println("NonFA._kstar: " + ((pass)?"Passes":"Fails") + "." );
		allPass = allPass && pass;
		pass = true;
		
		//evaluateTop() - v
		//needs some stuff on the stacks

		if( allPass ) {
			//test each part individually

			List<State2> utest, ktest, ctest;
			nfa = new NonFA();
			nfa._push('a');
			nfa._push('b');
			nfa.operators.push('|');
			pass = pass && nfa.evaluateTop();
			if (pass) {
				pass = pass && nfa.opperands.size() == 1;
				if (pass) {
					utest = nfa.opperands.pop();
					pass = pass && utest.size()==6;
				}
			}

			while( nfa.opperands.size() > 0 ) nfa.opperands.pop();

			if (pass) {
				nfa._push('a');
				nfa.operators.push('*');
				pass = pass && nfa.evaluateTop();
				if (pass) {
					pass = pass && nfa.opperands.size() == 1 ;
					if (pass) {
						ktest = nfa.opperands.pop();
						pass = pass && ktest.size()==4;
					}
				}
			}

			if (pass) {
				nfa._push('a');
				nfa._push('b');
				nfa.operators.push('+');
				pass = pass && nfa.evaluateTop();
				if (pass) {
					pass = pass && nfa.opperands.size() ==1 && nfa.operators.size()==0;
					if (pass) {
						ctest = nfa.opperands.pop();
						pass = pass && ctest.size()==4;
					}
				}
			}
		}

		System.out.println("NonFA.evaluateTop: " + ((pass)?"Passes":"Fails") + ".");
		allPass = allPass && pass;
		pass = true;
		
		//prescedence() - r
		//just need to make sure the values are correct.

		Character star = '*',
				  unio = '|',
				  conc = '+';
		nfa = new NonFA();

		pass = pass && nfa.prescedence( unio, star );
		pass = pass && nfa.prescedence( star, star );
		pass = pass && !nfa.prescedence( star, unio);
		pass = pass && nfa.prescedence ( conc, star);
		pass = pass && nfa.prescedence ( unio, conc);
		pass = pass && !nfa.prescedence (conc, unio);

		System.out.println("NonFA.precedence: " + ((pass)?"Passes":"Fails") + ".");
		allPass = allPass && pass;
		pass = true;
		
		//regexExpand() - e
		//needs a regex in the less verbose form
		//compare against doing it manually

		nfa = new NonFA();
		String pre = "ab(c|d)e*[a-h]*f";
		String target = "a+b+(c|d)+e*+(a|b|c|d|e|f|g|h)*+f";
		String result = nfa.regexExpand(pre);

		pass = pass && (result != null);
		if (pass) {
			pass = pass && result.equals(target);
			if (!pass) {
				System.out.println("  Pre-Ex: " + pre);
				System.out.println("  Target: " + target);
				System.out.println("  Result: " + result);
			}
		}
		else System.out.println("  Result is null.");

		allPass = allPass && pass;
		pass = true;
		
		//buildFromRegex(String) - b
		//should do basically everything based only on a regex
		
		nfa = new NonFA();
		String regex = "ab(c|d)e*[a-h]*f";
		pass = pass && nfa.buildFromRegex(regex);

		pass = pass && (nfa.states.size()==48);
		int count_accepts = 0,
			count_epsilons = 0;
		

		if( pass ) {
			Integer tmp;
			for( State2 s : nfa.states ) {
				count_accepts += (s.isAccepting())?1:0;
				tmp = (s.getTargets(EPSILON)!=null)?s.getTargets(EPSILON).size():0;
				count_epsilons += tmp;
			}
			pass = pass && count_accepts == 1;
			pass = pass && count_epsilons == 45;
		}

		System.out.println("NonFA.buildFromRegex: " + ((pass)?"Passes":"Fails") + ".");
		allPass = allPass && pass;
		
		System.out.println("The test program finishes " + ((!allPass)?"with":"without") + " errors.");

		System.out.println();
		System.out.println( "The regex used for final tests was: " + regex + "." );
		System.out.println( "The final NFA has " + ((Integer)nfa.states.size()) + " states.");
		System.out.println( "The final NFA has " + ((Integer)count_epsilons) + " epsilon transformations.");
		System.out.println( "That means that short of building and comparing the entire table, ");
		System.out.println( " the NFA is correct." );

		test_other();
        
        
        test_janzen();

	}

	public String toString() {
		String out = "";
		out += "Start state: " + states.get(0).getID() + "\n";
		out += "# states: " + states.size() + "\n";
		out += "alphabet:" + "\n";
		for (Character c : input_set) out += c + " ";
		out += "\n";
		out += "states:" + "\n";
		for (State2 s : states) {
			out += s + "\n";
		}
		return out;
	}
	

};
